package 树.递归;
/*
 解题思路：
PS:这题没太抓住细节，日后再看一下官方题解


    该题还是遵循“找到一个节点该做的事情，剩下的交给递归框架”。
    递归很重要的一点就是找到最简单的子问题。我们可以设想一下，一棵树s就三个节点，root、left、right。我们要做的就是找到首先以root为根节点的子树，看他是否在t中有相同结构，再就是找到以left为根节点...right也是同理..。
    所以我们就构造一个辅助函数去对比，两颗子树的结构是不是相同。要注意的是假如现在是以root为根节点嘛。我们比较的时候应该比较的是一颗完整的子树结构，即 这颗s的子树应该是[root,left,right]这才叫一颗完整的子树。
再比如现在以left为根节点，那么现在完整的子树应该为[left,left.left,left.right]。

    这三个都要比较，只有这三个都能在t中对应起来，才能说s中有一颗完整的子树在t中存在相同结构的子树。

 */
public class 另一个树的子树_572 {
    public boolean isSubtree(TreeNode s, TreeNode t) {

        if (t == null) return true;   // t 为 null 一定都是 true:空树为任何树的子树
        if (s == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false


        boolean rootFlag = help(s, t);//s也是s的子树，看s这颗子树是否在t中有相同结构的子树


        boolean leftFlag = isSubtree(s.left, t);
        boolean rightFlag = isSubtree(s.right, t);

        return leftFlag || rightFlag || rootFlag;//只要s这一整棵树中， 有一种子树在t中有相同结构的子树，就应该返回true。
    }


    public boolean help(TreeNode s, TreeNode t) {//判断两棵树是否相同
        //base case
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;

        //一个节点要做的事情
        if (s.val != t.val) return false;

        boolean leftFlag = help(s.left, t.left);
        boolean rightFlag = help(s.right, t.right);

        return leftFlag && rightFlag;//因为是要求“具有相同结构和节点值”，所以必须要左子树返回的值为true，右子树返回的值也为true，即该节点，该节点的左子树，该节点的右子树（他们仨合起来称成为了一颗完整的s的子树），都可以在t中找到相同结构的子树。

    }
}
